public class IsPalindrome3 {

    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode headNew = revers(slow);
        ListNode temp = headNew;
        while (temp != null) {
            if (head.val != temp.val) {
                revers(headNew);
                return false;
            }
            head = head.next;
            temp = temp.next;
        }
        revers(headNew);
        return true;
    }

    public ListNode revers(ListNode head) {
        ListNode dummyHead = new ListNode();
        ListNode temp = head;
        while (temp != null) {
            ListNode next = temp.next;
            temp.next = dummyHead.next;
            dummyHead.next = temp;
            temp = next;
        }
        return dummyHead.next;
    }
}
